目录

一、哈希表基础知识

　　1. 哈希表基本概念

二、哈希表相关题目

一、哈希表基础知识

1. 哈希表基本概念

　　哈希表(Hash Table)是根据关键码值(key, value)而直接进行访问的数据结构。当我们从哈希表中查找需要的数据时，理想情况是不经过任何比较，一次存取便能得到所查记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中唯一的存储位置对应。

　　可以把哈希表理解为一个数组，每个索引对应一个存储位置，哈希表的索引并不像普通数组的索引那样，从0到length-1.而是关键字(key)本身通过哈希函数得到。

举例说明：

　　将26个小写字母存储到数组 int a[26]中。

　　a对应a[0], b对应a[1]，c对应a[2]，....以此类推

 　　哈希函数

　　上述例子中，关键字（小写字母）是如何得到自己对应索引的位置的呢

　　关键字的ASCII值减去a的ASCII值。

 　　之前说过，关键字通过哈希函数得到索引，所以，f(ch)就是哈希函数。

二、哈希表相关题目

　　1.1 第一次只出现一次的字符

　　要统计第一个只出现一次的字符，可以利用哈希表，遍历字符串两次

　　第一次：从头到尾遍历整个字符串，并统计每个字符出现的次数

　　第二次：再遍历字符串，在哈希表中找到首个数量为1的字符，并返回

　　为了实现哈希表，我们可以利用数组来进行实现。由于字符串中都是小写字母，因此我们申请一个长度为26的字符（一共有26个小写字母）。为了实现哈希表，我们将26个小写字母存储到数组word中，a对应a[0],b对应a[1],c对应a[2]，...以此类推。

　　此时word[26]就是一个哈希表。但是小写字母如何得到自己索引呢？由于每个小写字母都有自己对应的ASCII码值，用每个小写字母的ASCII码值减去97即a的ASCII码值，就可以得到小写字母的索引位置。数组的元素存储每个小写字母出现的次数。